import java.util.*;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025/2/17
 */
public class leetcode_143 {
    public static void main(String[] args) {
        reorderList(new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5))))));
    }

    public static void  reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // Step 1: 使用快慢指针找到链表的中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        ListNode tmp;
        ListNode tmpLeft;
        slow.next = null;
        while(cur!=null){
            tmp = cur;
            cur = cur.next;
            tmp.next = null;
            tmpLeft = slow.next;
            slow.next = tmp;
            tmp.next = tmpLeft;
        }

        ListNode left = head;
        ListNode right = slow.next;
        slow.next=null;
//        ListNode tmpLeft;
        ListNode tmpRight;
        while(left!=slow&&right!=null){
            tmpRight = right;
            right = right.next;
            tmpRight.next = null;
            tmpLeft=left.next;
            left.next = tmpRight;
            tmpRight.next = tmpLeft;
            left = tmpLeft;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            // s 相同的字符串分到同一组
            m.computeIfAbsent(new String(s), k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }
}